"""
    create by IAmFiveHigh on 2023/9/5
"""


class Node:
    def __init__(self, element, next=None):
        self.e = element
        self.next = next

    def __str__(self):
        return f"Node: [{self.e}]"


class LinkList:
    def __init__(self):
        self._dummy_head = Node(None)
        self._size = 0

    def get_size(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def add(self, index, element):
        self._guard_index_legal(index)

        prev = self._dummy_head
        # 循环找到对应index之前的那个节点
        for i in range(index):
            prev = prev.next

        node = Node(element, prev.next)
        prev.next = node
        self._size += 1

    def add_first(self, element):
        self.add(0,element)

    def add_last(self, element):
        self.add(self._size, element)

    def set(self, index, element):
        self._guard_index_legal(index)

        cur = self._dummy_head.next
        for i in range(index):
            cur = cur.next
        cur.e = element

    def get(self, index):
        self._guard_index_legal(index)

        cur = self._dummy_head.next
        for i in range(index):
            cur = cur.next
        return cur.e

    def get_first(self):
        return self.get(0)

    def get_last(self):
        return self.get(self._size - 1)

    def contain(self, element) -> bool:
        cur = self._dummy_head.next
        while cur is not None:
            if cur.e == element:
                return True
            cur = cur.next
        return False

    def remove(self, index):
        pre = self._dummy_head
        for i in range(index):
            pre = pre.next
        del_node = pre.next
        pre.next = del_node.next
        del_node.next = None

        self._size -= 1

        return del_node.e

    def remove_first(self):
        self.remove(0)

    def remove_last(self):
        self.remove(self._size - 1)

    def __str__(self):
        description = ""
        cur = self._dummy_head.next
        while cur is not None:
            description += f"{str(cur.e)} -> "
            cur = cur.next
        description += "None"
        return description

    def _guard_index_legal(self, index):
        if index < 0 or index > self._size:
            raise Exception("index参数不合法")